Faraz Zaidi, Labri, INRIA
Bordeaux - Sud Ouest, faraz.zaidi@labri.fr [PRIMARY contact]
Paolo
Simonetto, Labri, INRIA Bordeaux - Sud Ouest,
paolo.simonetto@labri.fr
Daniel Archambault, INRIA Bordeaux - Sud
Ouest, daniel.archambault@inria.fr
Pierre-Yves Koenig, Labri,
INRIA Bordeaux - Sud Ouest, Pierre-Yves.Koenig@labri.fr
Frédéric
Gilbert, Labri, INRIA Bordeaux - Sud Ouest, frederic.gilbert@labri.fr
Trung-Tien Phan-Quang, Labri, INRIA Bordeaux - Sud Ouest,
phanquan@labri.fr
Ronan Sicre, Labri, sicre@labri.fr
Mathieu
Brulin, Labri, mathieu.brulin@labri.fr
Remy Vieux, Labri,
vieux@labri.fr
Morgan Mathiaut, Labri, mathiaut@labri.fr
Antoine
Lambert, Labri, antoine.lambert@labri.fr
Guy Melançon,
LaBRI,
INRIA Bordeaux - Sud Ouest, [Faculty
adviser]
The Tulip
framework allows for the visualization, drawing, and editing of
graphs. All the parts of the framework have been built in order to
visualize graphs of more than 1,000,000 elements. The system allows
navigation, geometric operations, extraction of subgraphs, metric
computations, graph theoretic operations, and filtering.
The Tulip
architecture provides the following features :
· 3D visualizations
· 3D modifications
· Plug-in support for easy evolution
· Building of clusters and navigation into it
· Automatic drawing of graphs
· Automatic clustering of graphs
· Automatic selection of elements
· Automatic Metric colouring of graphs
Video:
ANSWERS:
MC2.1: Which of the two social structures, A or B, most closely match the scenario you have identified in the data?
B
MC2.2: Provide the social network structure you have identified as a tab delimited file. It should contain the employee, one or more handler, any middle folks, and the localised leader with their international contacts. What are the Flitter names of the persons involved? Please identify only key connections (not all single links for example) as well as any other nodes related to the scenario (if any) you may have discovered that were not described in the two scenarios A and B above.
MC2.3: Characterize the difference between your social network and the closest social structure you selected (A or B). If you include extra nodes please explain how they fit in to your scenario or analysis.
The closest network structure we found in the data is similar to scenario B. This network has exactly the same connectivity with the employee connected to the three handlers, each handler connected to their own middleman, and the three middlemen connected to the fearless leader.
Here is how we proceed towards obtaining this solution.
First, we select employee based on degree range. The degree of an employee is about 40. We start by plotting degree distribution histograms as shown in figure 1. From these histograms, we see that few nodes have a degree above 45, and, therefore, we can safely take 45 as an upper bound for employee degree. We take the same level of uncertainty as a lower bound for employee degree.
figure 1
Next, we select the possible handler candidates based on the degree range where 30 and 40 is specified. We consider the range 27 and 43, ensuring that no solution near these upper and lower bounds are missed.
The maximum degree for a middleman is probably about 6. We know that these middlemen communicate with one or more handlers, and the maximum number of handlers is 3. Additionally, middlemen communicate with one or two other contacts with one of these contacts being the fearless leader. Therefore, a middleman can have a degree of about 5 (3 handlers + 1 or 2 other contacts). Thus, we set the degree of a middleman to 6, once again overestimating degree rather than underestimating it.
Finally, the fearless leader has over 100 contacts. We set this lower bound, giving us a set of possible fearless leaders in the network.
Once we have identified sets of candidates for each possible role, we compute the induced subgraph between all of them filter the network. Using this induced subgraph, we search for the criminal network. We have a number of constraints that can help us. Firstly, the number nodes of a certain role in a criminal network is limited. For example, in a criminal network we only have one employee and three handlers. Secondly, the connectivity between these candidates is restricted.
To specify these constraints, we have a general system for constructing template criminal networks, allowing us to draw the criminal network by hand. The system is shown in figure 2. Any number of nodes for each role can be inserted into the diagram and we connect these nodes with required or optional edges. If two nodes are disconnected in this template network, connections between these nodes are disallowed.
figure 2
In the task description, there is an employee, 3 handlers, 1 to 3 middlemen, and a fearless leader. In the criminal network, handlers may possibly communicate directly with fearless leader. Moreover, the number of middlemen is uncertain as each handler can have one middleman or the handlers may share one or two middlemen. Drawing the template criminal network introduces local degree constraints on each role as well. For example, an employee has a minimum degree of 3 in the criminal network, a fearless leader must have a degree of at least 1, and handlers and middlemen have a minimum degree of 2. Once we have constructed this template criminal network, our algorithm searches for this template inside the induced subgraph by tracing forward from employee candidates. Our system found about twenty possible solutions that can be filtered by hand.
We associate shapes to identify each role separately as follows: squares for employees, circles for handlers, triangles for middlemen, and pentagons for fearless leaders. The most significant constraint that allowed us to reduce number of networks was that a handler is directly connected to an employee and communicates to the the fearless leader either directly or through a middleman. In any of the candidate networks, if we find a fearless leader doesn't communicate with at least three handlers then the candidate network is rejected.
Once we have applied all these constraints, we have a set of possible solutions that cannot be filtered further using only the information present in part one of this task. To filter this list of solutions further, we use the geospatial information provided in part two. Nodes in the criminal network are coloured by city size according to the legend on the Flovania map. Distances between cities are mapped to edge width where thicker edges correspond to nodes that are close geospatially. An example network is shown in figure 3.
The two additional pieces of information that we use to filter our networks is:
The leader is in a larger city, meaning they are only in
cities that are marked in yellow or red.
A middleman is in a city
geospatially close to the employee or to the handler.
We apply these filters to the network presented in figure 3 and the resultant network is shown in figure 4.
figure 3
The network presented in Figure 4 is the closest network we found to either scenario. The network satisfies all topological and geospatial constraints with the exception that two of the middlemen have a slightly elevated degree of 6 in the Flitter network.
figure 4
MC2.4: How is your hypothesis about the social structure in Part 1 supported by the city locations of Flovania? What part(s), if any, did the role of geographical information play in the social network of part one?
The geospatial information provided in part two helped us further refine our solutions. A fearless leader needs to be in large city and handlers need to be close, in a geospatial sense, to their corresponding middlemen. Additionally, the map only contains two large cities: Koul and Prounov. Thus, all solutions that did not have a fearless leader in one of these cities were eliminated. Also, any solution which required a handler/middleman pair to be geospatially distant was eliminated. Thus, we filtered the number of possible solutions to a single criminal network which matched scenario B shown in figure 4. In this network, the embassy employee is close to the three handlers. The network also allows for the fearless leader to have middlemen spread out all over Flovania as shown in Figure 5.
figure 5
MC2.5: In general, how are the Flitter users dispersed throughout the cities of this challenge? Which of the surrounding countries may have ties to this criminal operation? Why might some be of more significant concern than others?
Figure 6 shows how the Flitter contacts are distributed over the given map. Node size is mapped to the number of Flitter users present in a given city. All the cities on the map have at least one Flitter user, and more Flitter users are present in larger cities than smaller ones.
figure
6
The fearless leader has ten international contacts from Otello, seven from Tulamuk, and five from Transpasko as shown in figure 7. As we assume that most transnational communications are made through the fearless leader, it would seem that Posana is of most concern followed by Trium. However, the majority of the activity appears to be in Flovania itself.
figure 7